
/////////////////////////////////////////////////////////////////////////////////
//
//  算法 ： 冒泡排序，新增 lastChangeIndex 记录最后发生交换的位置，减少减少内循环，外循环的次数。
//
/////////////////////////////////////////////////////////////////////////////////

#include<iostream>


// 新增 lastChangeIndex 记录最后发生交换的位置，减少循环次数
void mySort(int arr[], int len)
{
    int tmp ;               // 临时变量，交换值用
    int m = len-1;          // 外层循环，从 len - 开始。
    int isChange = 1;       // 内循环是否发生交换，没有交换，已经排序好，可以直接推出。
    int lastChangeIndex = 0;// 内循中发生交换的位置， 外部 m = lastChangeIndex ,可以跳过 排好序的部分。减少内循环，外循环的次数。
    while(m>0 && isChange)
    {
        isChange = 0;
        lastChangeIndex = 0;
        for (int j = 0; j <m;j++)
        {
            if (arr[j] > arr[j+1] )
            {
                isChange = 1;
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                lastChangeIndex = j;
            }
        }
        m=lastChangeIndex;

        std::cout<< "seq "<< m <<": ";
        for (int j = 0; j < len;j++)
        {
            std::cout << arr[j] << " " ;
        }
        std::cout << std::endl;
        if(isChange == 0)
            break;
    }
}

int main()
{
    int iarr[] = {1,2,9,5,3,8,6};
    int len = sizeof(iarr) / sizeof(iarr[0]);

    for (int i = 0; i < len;i++)
    {
        std::cout << iarr[i] << " " ;
    }
    std::cout << std::endl;
    mySort(iarr,len);
    for (int i = 0; i < len;i++)
    {
        std::cout << iarr[i] << " " ;
    }
    return EXIT_SUCCESS;
}
